l 1 l_1 l1​-norm， 作为 l 0 l_0 l0​-norm 的最紧凸近似，在压缩感知中非常常用。 例如求解问题： a r g m i n x A x = b s . t . ∣ x ∣ 0 ≤ n \mathrm{argmin}_x Ax = b \quad \mathrm{s.t.} |x|_0\le n argminx​Ax=bs.t.∣x∣0​≤n 即待求解向量 x x x是一个稀疏向量， 其非零元素个数不超过 n n n个。 一种基于LASSO的做法是将问题改写为： a r g m i n x ∣ ∣ A x − b ∣ ∣ 2 2 + λ ∣ x ∣ 1 \mathrm{argmin}_x ||Ax-b||_2^2 + \lambda |x|_1 argminx​∣∣Ax−b∣∣22​+λ∣x∣1​ 其中 λ \lambda λ是一个人工变量， 可通过改变其大小改变对稀疏条件的重视程度。 注意， 这里将不可导、非凸的零范数放松为了一范数。 也因此，改写后的问题是一个可导的问题。

最简单的情况下， x x x为实数向量。 此时， 1-范数的导数很容易由定义得到： ∣ x ∣ 1 = ∑ ∣ x i ∣ |x|_1=\sum |x_i| ∣x∣1​=∑∣xi​∣, ∂ ∣ x ∣ 1 x i = s i g n ( x i ) \frac{\partial |x|_1}{x_i} = \mathrm{sign}(x_i) xi​∂∣x∣1​​=sign(xi​).

本文考虑的是通信中更常见的情形， 即 x x x是一个复数向量。 此时， ∣ x i ∣ |x_i| ∣xi​∣不再是 x i x_i xi​的绝对值， 而是复数 x i x_i xi​的模，即 x i x i ∗ \sqrt{x_ix_i^*} xi​xi∗​ ​. 也就是说：(复数时求梯度为对变量的共轭求导） ∂ ∣ x ∣ 1 ∂ x i ∗ = ∂ ∑ x i x i ∗ ∂ x i ∗ = ( x i ) 1 2 ( x i ∗ ) − 1 2 2 . \frac{\partial |x|_1}{\partial x_i^*}=\frac{\partial \sum \sqrt{x_ix_i^*}}{\partial x_i^*} = \frac{(x_i)^\frac{1}{2}(x^*_i)^{-\frac{1}{2}}}{2}. ∂xi∗​∂∣x∣1​​=∂xi∗​∂∑xi​xi∗​ ​​=2(xi​)21​(xi∗​)−21​​.

进一步更复杂一些的： 设 f = ∣ A x ∣ 1 f = |Ax|_1 f=∣Ax∣1​， 求 ∂ f ∂ x ∗ \frac{\partial f}{\partial x^*} ∂x∗∂f​。 设 A A A的第 i i i行为 a i a_i ai​, 那么 [ A x ] i = a i x [Ax]_i=a_ix [Ax]i​=ai​x, ∣ [ A x ] i ∣ = ( x H a i H a i x ) 1 2 |[Ax]_i|=(x^Ha_i^Ha_ix)^{\frac{1}{2}} ∣[Ax]i​∣=(xHaiH​ai​x)21​, 因此， f = ∑ ( x H a i H a i x ) 1 2 f = \sum (x^Ha_i^Ha_ix)^{\frac{1}{2}} f=∑(xHaiH​ai​x)21​ 对 f f f求微分， 有： d f = d t r ( ∑ ( x H a i H a i x ) 1 2 ) = t r ( ∑ d ( x H a i H a i x ) 1 2 ) df=d\mathrm{tr}(\sum (x^Ha_i^Ha_ix)^{\frac{1}{2}})=\mathrm{tr}(\sum d(x^Ha_i^Ha_ix)^{\frac{1}{2}}) df=dtr(∑(xHaiH​ai​x)21​)=tr(∑d(xHaiH​ai​x)21​) 而： d ( x H a i H a i x ) 1 2 = 1 2 ( x H a i H a i x ) − 1 2 ( d x H ) a i H a i x d(x^Ha_i^Ha_ix)^{\frac{1}{2}} = \frac{1}{2}(x^Ha_i^Ha_ix)^{-\frac{1}{2}}(d x^H) a_i^Ha_ix d(xHaiH​ai​x)21​=21​(xHaiH​ai​x)−21​(dxH)aiH​ai​x 代回， 得： d f = t r ( ∑ 1 2 ( x H a i H a i x ) − 1 2 a i H a i x ( d x H ) ) df =\mathrm{tr}(\sum \frac{1}{2}(x^Ha_i^Ha_ix)^{-\frac{1}{2}}a_i^Ha_ix(d x^H) ) df=tr(∑21​(xHaiH​ai​x)−21​aiH​ai​x(dxH)) 因此， ∂ f ∂ x ∗ = 1 2 ∑ ( x H a i H a i x ) − 1 2 a i H a i x . \frac{\partial f}{\partial x^*} =\frac{1}{2} \sum (x^Ha_i^Ha_ix)^{-\frac{1}{2}}a_i^Ha_ix. ∂x∗∂f​=21​∑(xHaiH​ai​x)−21​aiH​ai​x.

再进一步的， 设 f = ∣ v e c ( A H X A ) ∣ 1 f = |\mathrm{vec}(A^HXA)|_1 f=∣vec(AHXA)∣1​， 求 ∂ f ∂ X ∗ \frac{\partial f}{\partial X^*} ∂X∗∂f​。 （注意， 如果 X X X是一个稀疏矩阵， 那么对其0范数的近似并不是直接 X X X的1范数， 而是 X X X向量化后的1范数。 因为一个矩阵的1范数是每列1范数的最大值， 而不是所有元素模的和。）

设 A A A的第 i i i列为 a i a_i ai​, 那么 [ A H X A ] i j = a i H X a j [A^HXA]_{ij} = a_i^HXa_j [AHXA]ij​=aiH​Xaj​, 由于 f f f代表矩阵每个元素的模的和， 因此 f = ∑ i ∑ j ( a j H X H a i a i H X a j ) 1 2 f = \sum_i\sum_j(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}} f=i∑​j∑​(ajH​XHai​aiH​Xaj​)21​ 同样地， 对 f f f求微分， 有：

d f = d t r ( ∑ i ∑ j ( a j H X H a i a i H X a j ) 1 2 ) = t r ( ∑ i ∑ j d ( a j H X H a i a i H X a j ) 1 2 ) df =d\mathrm{tr}(\sum_i\sum_j(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}})=\mathrm{tr}(\sum_i\sum_j d(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1} {2}}) df=dtr(i∑​j∑​(ajH​XHai​aiH​Xaj​)21​)=tr(i∑​j∑​d(ajH​XHai​aiH​Xaj​)21​)

而： d ( a j H X H a i a i H X a j ) 1 2 = 1 2 ( a j H X H a i a i H X a j ) − 1 2 a j H ( d X H ) a i a i H X a j d(a_j^HX^Ha_ia_i^HXa_j)^{\frac{1}{2}} = \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_j^H(dX^H)a_ia_i^HXa_j d(ajH​XHai​aiH​Xaj​)21​=21​(ajH​XHai​aiH​Xaj​)−21​ajH​(dXH)ai​aiH​Xaj​, 代回得

d f = t r ( ∑ i ∑ j 1 2 ( a j H X H a i a i H X a j ) − 1 2 a i a i H X a j a j H ( d X H ) ) df = \mathrm{tr}(\sum_i\sum_j \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_ia_i^HXa_ja_j^H(dX^H)) df=tr(i∑​j∑​21​(ajH​XHai​aiH​Xaj​)−21​ai​aiH​Xaj​ajH​(dXH)) 因此， ∂ f ∂ X ∗ = ∑ i ∑ j 1 2 ( a j H X H a i a i H X a j ) − 1 2 a i a i H X a j a j H . \frac{\partial f}{\partial X^*} = \sum_i\sum_j \frac{1}{2}(a_j^HX^Ha_ia_i^HXa_j)^{-\frac{1}{2}}a_ia_i^HXa_ja_j^H. ∂X∗∂f​=i∑​j∑​21​(ajH​XHai​aiH​Xaj​)−21​ai​aiH​Xaj​ajH​.